
//判断一个数组是否为二叉搜索树的后序遍历---2018.2.1

//首先，二叉搜索树的元素大小特点为：（1）左子树的所有元素均小于根节点元素；（2）右子树的所有元素均大于等于根节点元素
//再者，后序遍历指的是：先后序遍历左子树，再后序遍历右子树，最后访问根节点。

//根据以上特性，可分析得到：
//（1）数组的最后一个元素一定为整个二叉搜索树的根节点；
//（2）若只存在左子树，那么数组元素（除根节点元素外）均小于根节点元素；
//（3）若只存在右子树，那么数组元素（除根节点元素外）均大于根节点元素（因为题目已规定二叉树中无重复元素）；
//（4）若左右子树都存在，那么数组元素从前往后可分为左子树部分（小于根节点）和右子树部分（大于根节点）。

//综上，可设置数组索引变量，每次从前向后遍历数组，直到索引值等于根节点索引值。根节点索引值从后依次向前。

bool VerifySquenceOfBST(vector<int> sequence) {
    int n=sequence.size();
    if(!n)
        return false;      //若数组为空，则返回false
    
    int i=0;
    while(--n)             //--n等价于：表达式的值减1，并且n的值减1
    {
        //类似于进程的等待
        while(sequence[i++]<sequence[n]);    //遍历左子树部分，若存在，元素值小于根节点
        while(sequence[i++]>sequence[n]);    //遍历右子树部分

        //经过上述操作，若数组前面的元素满足上述条件，那么就符合二叉搜索树的后序遍历特点
        //此时，i的值与n相等。i++等同于：表达式的值为i，然后i再加1

        if(i<size)
            return false;
        
        i=0;     //重新从数组起点开始遍历
    }
    return true;
}
